package cn.ff.leetcode;


/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 */
public class MaxSubArray {

    public static void main(String[] args) {
        int[] ums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new MaxSubArray().maxSubArray(ums));
    }

    //贪心算法
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int pre = 0;
        for(int i:nums){
            pre = Math.max(pre+i,i);//可以计算出子数组初始值
            max = Math.max(max,pre);
        }
        return max;
    }
}